package day0411

func generateMatrix(n int) (ans [][]int) {
	row, column := 0, 0
	total := n * n
	cnt := 0
	directionIndex := 0
	// 初始化
	directions := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}

	visited := make([][]bool, n)
	for i := 0; i < n; i++ {
		visited[i] = make([]bool, n)
	}

	ans = make([][]int, n)
	for i := 0; i < n; i++ {
		ans[i] = make([]int, n)
	}

	for i := 0; i < total; i++ {
		visited[row][column] = true
		cnt++
		ans[row][column] = cnt
		// 探索下一个位置， 位置不合法 ，换方向
		nextRow, nextColumn := row+directions[directionIndex][0], column+directions[directionIndex][1]
		if nextRow < 0 || nextColumn < 0 || nextColumn >= n || nextRow >= n || visited[nextRow][nextColumn] {
			directionIndex++
			directionIndex %= 4
		}
		row, column = row+directions[directionIndex][0], column+directions[directionIndex][1]
	}
	return
}
